package com.zlk.algorithm.algorithm.sort.practice;

import com.zlk.algorithm.algorithm.sort.SortUtils;
import org.junit.Test;

import java.util.Arrays;

/**
 * @program: algorithm
 * @ClassName MergeSort
 * @description:
 * @author: slfang
 * @create: 2024-12-12 21:16
 * @Version 1.0
 **/
public class MergeSort {


    public void mergerSort(int[] arr){
        if(arr==null||arr.length<=1){
            return ;
        }
        int len = arr.length;
        mergerSort(arr,0,len-1);

    }

    private void mergerSort(int[] arr, int l, int r) {
        if(l>=r){
            return ;
        }
        int mid = l+(r-l)/2;
        mergerSort(arr,l,mid);
        mergerSort(arr,mid+1,r);
        merger(arr,l,r,mid);
    }

    private void merger(int[] arr, int l, int r,int mid) {
        int len = r-l+1;
        int[] temp = new int[len];
        int lIndex = l;
        int rIndex = mid+1;
        int index = 0;
        // 1  2 5 3  4
        // 0  1 2
        while (lIndex<=mid&&rIndex<=r){
            temp[index++] = arr[lIndex]<=arr[rIndex]?arr[lIndex++]:arr[rIndex++];
        }
        while (lIndex<=mid){
            temp[index++] =arr[lIndex++];
        }
        while (rIndex<=r){
            temp[index++] =arr[rIndex++];
        }

        for (int i = 0; i <len ; i++) {
            arr[l+i] = temp[i];
        }
    }

    @Test
    public void test (){
        int testTime = 500000;
        int maxSize = 30;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = SortUtils.getRandomArr(maxValue, maxSize);
            int[] arr2 = Arrays.copyOf(arr1,arr1.length);
            mergerSort(arr1);
            Arrays.sort(arr2);
            if (!SortUtils.isEqual(arr1, arr2)) {
                System.out.println("fail");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                return ;
            }
        }
        System.out.println("success");
    }
}
